// m

// 给定一个数组nums，数组中值互不相同，数组中的值经过了升序排列又进行了旋转，再给定一个target
// 要求从nums中找到target所在位置，如果找到，则返回对应下标，找不到则返回-1

// 思路：二分查找
// 数组nums经过旋转之后，会有两种情况：一种是原先的升序序列，另一种是两端升序的序列

// left和right两个指针分别指向数组首尾,然后计算出中间值mid,将mid与两个指针比较,并考虑与target的关系


// 时间复杂度：O(logn)
// 空间复杂度：O(1)
function search(nums, target) {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2)
        if (nums[mid] === target) {
            return mid 
        }
        if (nums[mid] >= nums[left]) {
            if (nums[mid] > target && target >= nums[left]) {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

let nums = [4, 5, 6, 7, 0, 1, 2]
let target = 0

console.log(search(nums, target))
